'''
https://leetcode.cn/problems/sort-array-by-parity-ii/description/
'''

from typing import List


class Solution:
    def sortArrayByParity(self, nums: List[int]) -> List[int]:
        n = len(nums)
        i, j = 0, n - 1
        while i < j:
            if nums[i] & 1:
                nums[i], nums[j] = nums[j], nums[i]
                j -= 1
            else:
                i += 1
        return nums

    def sortArrayByParityII(self, nums: List[int]) -> List[int]:
        n = len(nums)
        i, j = 0, 1
        while i < n and j < n:
            if nums[n - 1] & 1:
                nums[j], nums[n - 1] = nums[n - 1], nums[j]
                j += 2
            else:
                nums[i], nums[n - 1] = nums[n - 1], nums[i]
                i += 2
        return nums


nums = [4, 2, 5, 7]
print(Solution().sortArrayByParityII(nums))
